The present invention relates to packet-switched communications networks, and more particularly to the estimation of traffic between all sources and destinations for use in the engineering and planning of a packet-switched communications network.
Several tasks in the area of traffic engineering and capacity planning of packet-switched communications networks require knowledge of source-destination traffic demands. One such task is the expansion or modification of the network. Given an existing network, network planners project increases in traffic demands or changes in the existing demands and determine the necessary expansion or modification to the network to support the projected traffic. Such expansion or modification may involve changing the existing topology, re-sizing previously existing network elements, adding or removing switches and links, and re-routing previously existing traffic. In order to make such expansions or modifications to an existing network, existing source-destination traffic demands must be quantified. Indeed, in most commercially available network dimensioning and capacity planning software tools, source-destination traffic demands are among the primary design input parameters.
Another network planning task requiring knowledge of existing source-destination traffic demands is contingency planning. In contingency planning, network planners examine the effect of potential link or node failures on the performance of an existing network. In a contingency planning study, planners model the network and simulate network behavior by failing certain links or nodes. They then re-route the affected source-destination traffic and re-compute network performance.
Yet another network planning task requiring knowledge of source-destination traffic demands is the addition of spare capacity to an existing network. By adding spare capacity, in the event of a failure the affected traffic can be re-routed while maintaining required performance levels.
A basic problem in the network planning area is that in practice existing source-destination traffic demands in a large packet-switched network are difficult to quantity. The existing source-destination traffic demands may be measured directly if the Management Information Bases (MIBs) at access devices support traffic MIB variables on a per-connection basis. For example, in a frame relay access device that supports a MIB with MIB variables that count the number of octets sent on a particular Data Link Control Identifier (DLCI), one can directly measure the source-destination traffic demands. However, such MIB variables are not always supported. Moreover, in a large network several factors make measuring traffic between all the sources and destinations impractical, undesirable, or infeasible, including (i) overheads of counters that need to be updated continuously at network devices, (ii) message passing and processing overheads of network management protocols such as Simple Network Management Protocol (SNMP), and (iii) the large number of source-destination combinations in a large network. In general, as the size of a network increases, the number of source-destination traffic measurements that must be made grows as the square of the number of nodes.
While it is difficult to directly measure source-destination traffic demands, other quantities can be measured more easily. For example, traffic coming into the network from outside the network at each node can be measured easily. Also, it is more practical and more feasible to measure the aggregate packet traffic on point-to-point links rather than source-destination routes since (i) the number of links is usually not excessive even in large networks and (ii) standard MIBs support MIB variables that record the amount of traffic sent on a port (and therefore on a link, since every link must be connected to a port).
It is desirable, therefore, to provide a method for estimating source-destination traffic demands in a packet-switched communications network based on quantities that can be measured easily and/or directly, such as point-to-point link traffic and incoming node traffic.
Some methods for estimating source-destination traffic have been developed for circuit-switched networks. For example, M. Tu, "Estimation of Point-to-Point Traffic Demand in the Public Switched Telephone Network,"IEEE Transactions on Communications, 42, 2/3/4, pp. 840-845, 1994, describes an iterative solution for estimating the magnitude of source-destination traffic demands in a circuit-switching network during a particular measurement time period. The problem is reduced to that of finding a solution for a set of linear equations. Depending on the number of links in the network and the number of node traffic measurements that are used, the method finds either a minimum-norm exact, or least-squares solution. Shortcomings of this method are (i) the method uses measurements from only a single time period, (ii) the accuracy of the solution is in proportion to the network connectivity, and (iii) the method may provide solutions that are not physically valid since the minimum-norm and least-squares solutions are not constrained. N. Kim, "A Point-to-Point Traffic Estimation from Trunk-Group and Office Measurements for Large Networks," in Proc. 13th International Teletraffic Congress, A. Jensen and V. B. Iversen (Eds.), pp. 465--469, North-Holland, 1991, discusses a similar iterative method.
P. S. Min, M. V. Hedge, and A. Rayes, "Estimation of Exogeneous Traffic Based on Link Measurements in Circuit-Switched Networks," IEEE Transactions on Communications, 43, 8, pp. 2381-2390, 1995, presents a more sophisticated method for estimating source-destination traffic demands in circuit-switching networks. This method makes use of observed call holding time and link blocking information and solves constrained quadratic and non-linear optimizations to obtain physically valid solutions. However, the method considers only one measurement time period to keep the computational costs down. The method also assumes that no route consists of more than two links and that the traffic is bidirectional.
As explained, the existing methods are inadequate for estimating source-destination traffic in packet-switched networks for several reasons. First, they were developed specifically for circuit-switched networks, whose operation and traffic patterns are fundamentally different from those of packet-switched networks. Second, these methods use only a single time period measurement for the practical sake of limiting the computational requirements. Third, some of these methods are extremely complex because they require solving non-linear optimization problems. Fourth, some of these methods provide solutions that are physically invalid because they do not constrain the optimization problem.
It is desirable, therefore, to provide a method for estimating source-destination traffic developed specifically for packet-switched communications networks. It is also desirable to provide a method for estimating source-destination traffic that uses multiple time periods because multiple time periods provide more measurement data. It is further desirable to provide a simple method for estimating source-destination traffic that scales for large networks and multiple time periods. It is even more desirable to provide such a method that reduces a potentially large estimation problem into a set of smaller problems that can be solved efficiently in real time.